package IC.lir;


import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import IC.lir.operands.*;

import util.Pair;
import util.LinkedList;

import IC.AST.DefaultVisitor;
import IC.AST.PropogatingVisitor;
import IC.AST.nodes.*;
import IC.Analyzer.SymTabEntry;
import IC.Analyzer.Types.*;
import IC.lir.LoweringContext.ContextKind;
import IC.lir.decl.*;
import IC.lir.instructions.*;
import IC.lir.instructions.BasicInstr.Ops;
import IC.lir.instructions.JumpInstr.JumpCondition;

/**
 * list of optimizations:
 * 1. let any expression be calculated in several ways:
 * 		a. Register - save the value to a given register
 * 		b. DoubleLabel - treat the expression as boolean and generate code
 * 			which branches to these labels according to the boolean value
 * 		c. AnyOperand - let the expression decide which type of operand to return
 * 
 * 2. Immediates return themselves and so are local variables. they do not
 * 		save them selves to registers. 
 * 
 * 3. The binary expression handler takes advantage of accumulation, and evaluates
 * 		the expressions so one has to be in a register and the other can be
 * 		in any operand. 
 * 
 * 4. If the operation is commutative - the order of the operations can be swapped
 * 		if one is "volunteraly" computed to a register
 *  
 * 5. The function call does not take any registers to save the parameters
 * 		but rather takes the computed arguments as AnyOperand
 * 
 * 6. The array index accepts both immediates and registers
 * 
 * 7. The comparison swaps the meaning of the labels, if needed, if one of
 * 		the operands is "volunteraly" computed to a register.
 * 
 *
 */
public class LoweringVisitor extends
		DefaultVisitor<LoweringContext, List<LIREntry>> implements
		PropogatingVisitor<LoweringContext, List<LIREntry>> {

	private static class DoubleLabel implements LoweringContext {
		public Label trueLabel;
		public Label falseLabel;

		/**
		 * 
		 * @param trueLabel
		 * @param falseLabel
		 */
		public DoubleLabel(Label trueLabel, Label falseLabel) {
			this.trueLabel = trueLabel;
			this.falseLabel = falseLabel;
		}

		public ContextKind getKind() {
			return ContextKind.DBLLabel;
		}
	}

	/**
	 * holds a context which propogate any operand
	 * can do "conversion" and return what is requested
	 * @author root
	 *
	 */
	private static class AnyOperand implements LoweringContext {
		private Operand op = null;
		private	Kind	kind;
		
		private enum Kind {
			Reg, Imm, Mem;
		}
		
		public void set(RegOperand op) 	{ this.op = op; kind = Kind.Reg; }
		public void set(MemOperand op) 	{ this.op = op; kind = Kind.Mem; }
		public void set(ImmOperand op) 	{ this.op = op; kind = Kind.Imm; }
		
		/**
		 * convert to register 
		 * @param list
		 * @return
		 */
		public RegOperand getReg(List<LIREntry> list) {
			assert(op != null);
			switch (kind) {
			case Reg:
				return (RegOperand)op;
			default:
				RegOperand Rtmp = new RegOperand();
				list.add(new MoveInstr(op, Rtmp));
				return Rtmp;
			}
		}
		
		public boolean isReg() {
			return kind.equals(Kind.Reg);
		}
		/**
		 * convert to register or immediate
		 * @param list
		 * @return
		 */
		public Operand getRegImm(List<LIREntry> list) {
			assert(op != null && list != null);
			
			switch (kind) {
			case Reg: case Imm:
				return op;
			default:
				RegOperand Rtmp = new RegOperand();
				list.add(new MoveInstr(op, Rtmp));
				return Rtmp;
			}
		}
		
		public Operand getOp() {
			assert(op != null);
			return op;
		}

		public ContextKind getKind() {
			return ContextKind.AnyOperand;
		}
	}
	
	/* loop start and end labels (for break, continus) */
	private Label loopTest, loopEnd;

	/* holds the program root */
	private Program root;
	
	
	

	/**
	 * Constructs a new visitor
	 */
	private LoweringVisitor() throws Exception {
	}
	

	/**
	 * Translates a program to LIR
	 * 
	 * @param root
	 *            the program
	 */
	public static void Process(Program root) throws Exception {
		LoweringVisitor v = new LoweringVisitor();
		PreProcessor.Process(root);
		v.root = root;
		root.accept(v, null);
	}

	public List<LIREntry> visit(Program that, LoweringContext context)
			throws Exception {
		for (ClassDecl cls : that.getClasses()) {
			if (!cls.getClassID().equals("Library")) {
				cls.accept(this, context);
			}
		}
		return null;
	}

	
	/**
	 *	if (a) then b; else c;
	 *	-----------------------		
	 *		visit(a,null,false)
	 *		visit(b)
	 *		jmp end
	 *	false:
	 *		visit(c)
	 *	end:
	 * 	
	 *  if a then b;
	 *	-------------
	 *		visit(a,null,false)
	 *		visit(b)
	 *	false:
	 *
	 */
	public List<LIREntry> visit(IfStmt that, LoweringContext context)
			throws Exception {

		RegOperand.resetCounter();
		
		// translate the condition
		Label labelFalse = new Label();
		List<LIREntry> list = that.getCondition().accept(this,
				new DoubleLabel(null, labelFalse));

		// translate the If statement
		list.addAll(that.getIfStmt().accept(this, null));

		if (that.getElseStmt() != null) {
			// add jump-to-end instruction
			Label labelEnd = new Label();
			list.add(new JumpInstr(labelEnd));
			list.add(new LabelDecl(labelFalse));
			list.addAll(that.getElseStmt().accept(this, null));
			list.add(new LabelDecl(labelEnd));
		} else {
			list.add(new LabelDecl(labelFalse));
		}
		return list;
	}

	
	/**
	 *	while (a) b;
	 *	------------
	 *		jump test
	 *	start:
	 *		visit(b)
	 *	test:
	 *		visit(a,start,null)
	 *	end:
	 *
	 */
	public List<LIREntry> visit(WhileStmt that, LoweringContext context)
			throws Exception {

		RegOperand.resetCounter();

		// create 3 labels: start, end, test
		Label labelStart = loopTest = new Label();
		Label labelTest = new Label();
		loopEnd = new Label();
		DoubleLabel dblLabel = new DoubleLabel(labelStart, null);

		// first, jump to `test' label
		List<LIREntry> list = new LinkedList<LIREntry>(new JumpInstr(labelTest));

		// then, add the loop restart label
		list.add(new LabelDecl(labelStart));

		// translate body
		list.addAll(that.getBody().accept(this, null));

		// translate condition
		list.add(new LabelDecl(labelTest));
		list.addAll(that.getCondition().accept(this, dblLabel));
		list.add(new LabelDecl(loopEnd));
		return list;
	}


	/** 
	 * visit a method - 
	 * save the method code
	 */
	public List<LIREntry> visit(MethodDecl that, LoweringContext context)
			throws Exception {

		// put the method label
		List<LIREntry> list = 
			new LinkedList<LIREntry>(new LabelDecl(that.getLabel()));

		// translate the method body (statement block)
		list.addAll(that.getBody().accept(this, null));

		// add 'Return 9999' instruction if the function is void
		if ((that.getReturnType() == null) && (that != root.getMain()))
			list.add(new ReturnInstr(new IntImmediate()));

		// save the code of this method
		that.setLirCode(list);
		return null;
	}
	
	
	/**
	 * visit a statement block - 
	 * concatinate all statements
	 */
	public List<LIREntry> visit(StmtBlock that, LoweringContext context)
			throws Exception {

		List<LIREntry> list = new LinkedList<LIREntry>();
		for (Statement s : that.getStmts()) {
			list.addAll(s.accept(this, null));
		}
		return list;
	}
	

	/**
	 * break;
	 * ------
	 * 		jump loopEnd
	 */
	public List<LIREntry> visit(BreakStmt that, LoweringContext context)
			throws Exception {
		return new LinkedList<LIREntry>(new JumpInstr(loopEnd));
	}
	

	/**
	 * continue;
	 * ---------
	 * 		jump loopTest
	 */
	public List<LIREntry> visit(ContinueStmt that, LoweringContext context)
			throws Exception {
		return new LinkedList<LIREntry>(new JumpInstr(loopTest));
	}
	

	/**
	 * a = b;
	 * -------
	 * 		translateAssignment( a <- b )
	 */
	public List<LIREntry> visit(AssignStmt that, LoweringContext context)
			throws Exception {
		RegOperand.resetCounter();
		return translateAssignment(that.getDest(), that.getSrc());
	}
	

	/**
	 * return a;
	 * ---------
	 * 		visit(a,Rinterm)
	 * 		Return a
	 * 
	 * return;
	 * -------
	 * 		Return 9999
	 * 
	 */
	public List<LIREntry> visit(ReturnStmt that, LoweringContext context)
			throws Exception {

		RegOperand.resetCounter();
		List<LIREntry> list;
		if (that.getExpr() != null) {
			AnyOperand res = new AnyOperand();
			list = that.getExpr().accept(this, res);
			list.add(new ReturnInstr(res.getOp()));
		} 
		else {
			list = new LinkedList<LIREntry>(
					new ReturnInstr(new IntImmediate()));
		}
		return list;
	}
	

	/**
	 * Type a;
	 * ------
	 * 
	 * Type a = b;
	 * -----------
	 * 		translateAssignment( a <- b )
	 *
	 */
	public List<LIREntry> visit(VarDeclStmt that, LoweringContext context)
			throws Exception {

		RegOperand.resetCounter();
		if (that.getInit() == null) {
			return new LinkedList<LIREntry>();
		} else {
			return translateAssignment(that.getVar(), that.getInit());
		}
	}
	

	/**
	 * a();
	 * ----
	 * 		visit(a,Rdummy)
	 * 
	 */
	public List<LIREntry> visit(MethodCallStmt that, LoweringContext context)
			throws Exception {

		RegOperand.resetCounter();
		return that.getCall().accept(this, RegOperand.getDummy());
	}
	

	/**
	 * A.m(e1,e2)
	 * ----------
	 * 		visit(e1, Rp1)
	 * 		visit(e2, Rp2)
	 * non-boolean:
	 * 		StaticCall _A_m(e1,e2), Rdest
	 * boolean:
	 * 		StaticCall _A_m(e1,e2), Rtmp
	 * 		addBranchCode(Rtmp, context)
	 * 
	 * 
	 * Library.m(e1,e2)
	 * ----------------
	 * 		visit(e1, Rp1)
	 * 		visit(e2, Rp2)
	 * non-boolean:
	 * 		Library		_A_m(e1,e2), Rdest
	 * boolean:
	 * 		Library		_A_m(e1,e2), Rtmp
	 * 		addBranchCode(Rtmp, context)
	 * 
	 * 
	 */
	public List<LIREntry> visit(StaticCall that, LoweringContext context)
			throws Exception {

		List<LIREntry> list = new LinkedList<LIREntry>();

		if (that.getClassID().equals("Library")) {
			/** handle Library calls */

			// build argument list
			List<Operand> params = new ArrayList<Operand>();
			for (Expression argExpr : that.getArgs()) {
				AnyOperand dest = new AnyOperand();
				list.addAll(argExpr.accept(this, dest));
				params.add(dest.getOp());
			}

			// emit the call
			switch (context.getKind()) {
			case REG:
			case AnyOperand:
				RegOperand Rtmp = getRegToSave(context);
				list.add(new LibraryInstr(that.getMethodID(), params, Rtmp));
				return list;
			case DBLLabel:
				RegOperand Rdest = new RegOperand();
				list.add(new LibraryInstr(that.getMethodID(), params, Rdest));
				addBranchCode(list, (DoubleLabel) context, Rdest);
				return list;
			default:
				assert(false);
				throw new Exception();
			}
		} 
		else {
			/** handle typical static calls * */

			// find method declaration
			ClassInfo classInfo = getClassInfo(that.getClassID());
			String methodID = that.getMethodID();
			SymTabEntry eMethod = classInfo.getClassDecl().
							getStaticSymTab().resolve(methodID);
			assert(eMethod != null);
			MethodDecl methodDecl = (MethodDecl) eMethod.getDeclNode();

			// build assiciative parameter list to the function
			List<Pair<String, Operand>> params = 
					buildParams(list, that.getArgs(), methodDecl);

			// branch on boolean and non-boolean expressions
			switch (context.getKind()) {
			case REG:
			case AnyOperand:
				RegOperand Rtmp = getRegToSave(context);
				list.add(new StaticCallInstr(
						new Label(methodDecl.getLabel()), params, Rtmp));
				return list;
			case DBLLabel:
				RegOperand Rdest = new RegOperand();
				list.add(new StaticCallInstr(
						new Label(methodDecl.getLabel()), params, Rdest));
				addBranchCode(list, (DoubleLabel) context, Rdest);
				return list;
			default:
				assert(false);
				throw new Exception();
			}
		}
	}
	

	/**
	 * [ o. ] a(e1,e2)
	 * --------------
	 * 		visit(o, Robj) |  Move	this, Robj
	 * 		visit(e1, Rp1)
	 * 		visit(e1, Rp2)
	 * 		VirtualCall Robj.offset-of-method(type-of(o|this),a)(params), Rdest
	 * 	if (boolean-context):
	 * 		Compare		1, Rdest
	 * 		JumpTrue	trueLabel
	 * 		JumpFalse	falseLabel
	 * 
	 */
	public List<LIREntry> visit(VirtualCall that, LoweringContext context)
			throws Exception {
		
		List<LIREntry> list;
		ClassInfo classInfo;
		RegOperand Robj = new RegOperand();

		// put instance to Rtmp and get classInfo
		Expression inst = that.getInstance();
		if (inst != null) {
			// Rtmp <- translate(o)
			list = inst.accept(this, Robj);
			classInfo = getClassInfoByExpr(inst);
		} else {
			// Rtmp <- this
			list = new LinkedList<LIREntry>();
			list.add(new MoveInstr(new MemOperand("this"), Robj));
			classInfo = 
				getClassInfoByType(that.getSymTab().resolve("this").getType());
		}

		// find method declaration
		String methodID = that.getMethodID();
		SymTabEntry eMethod = classInfo.getClassDecl().getSymTab().resolve(
				methodID);
		MethodDecl methodDecl = (MethodDecl) eMethod.getDeclNode();

		// build assiciative parameter list to the function
		List<Pair<String, Operand>> params = 
				buildParams(list, that.getArgs(), methodDecl);

		// find method offset
		ImmOperand offs = 
			new IntImmediate(classInfo.getMethodOffset(methodID));

		// branch on boolean and non-boolean expressions
		switch (context.getKind()) {
		case REG:
		case AnyOperand:
			RegOperand Rtmp = getRegToSave(context);
			list.add(new VirtualCallInstr(Robj, offs, params, Rtmp));
			return list;
		case DBLLabel:
			RegOperand Rdest = new RegOperand();
			list.add(new VirtualCallInstr(Robj, offs, params, Rdest));
			addBranchCode(list, (DoubleLabel) context, Rdest);
			return list;
		default:
			assert(false);
		}
		throw new Exception();
	}

	
	/**
	 * a[i]
	 * ----
	 * lvalue:
	 * 		visit(a, Rarr)
	 * 		visit(i, Rindex)
	 * 		MoveArray	Rsrc, Rarr[Rindex]
	 * 	
	 * rvalue (boolean):
	 * 		visit(a, Rarr)
	 * 		visit(i, Rindex)
	 * 		MoveArray	Rarr[Rindex], Rtmp
	 * 		Compare		1, Rtmp
	 * 		JumpTrue	labelTrue
	 * 		JumpFalse	labelFalse
	 * 
	 * rvalue (non-boolean):
	 * 		visit(a, Rarr)
	 * 		visit(i, Rindex)
	 * 		MoveArray	Rsrc, Rarr[Rindex]
	 * 		MoveArray	Rarr[Rindex], Rdest
	 * 
	 */
	public List<LIREntry> visit(ArrayElmVar that, LoweringContext context)
			throws Exception {
		// put array pointer to a register
		RegOperand Rarr = new RegOperand();
		List<LIREntry> list = that.getArray().accept(this, Rarr);

		// put array index to a register
		AnyOperand index = new AnyOperand();
		list.addAll(that.getIndex().accept(this, index));

		if (that.isLvalue()) {
			// Rarr[Rindex] <- source
			switch (context.getKind()) {
			case REG:
				list.add(new MoveToArrayInstr((RegOperand)context, 
								Rarr, index.getRegImm(list)));
				break;
			case AnyOperand:
				Operand tmp = ((AnyOperand)context).getRegImm(list);
				list.add(new MoveToArrayInstr(tmp, Rarr, index.getRegImm(list)));
				break;
			}
		} 
		else {
			RegOperand Rtmp;
			switch (context.getKind()) {
			case REG:
			case AnyOperand:
				RegOperand Rdest = getRegToSave(context);
				// dest <- Rarr[Rindex]
				list.add(new MoveFromArrayInstr(Rarr, index.getRegImm(list), Rdest));
				break;
			case DBLLabel:
				// Rtmp <- Rarr[Rindex]
				Rtmp = new RegOperand();
				list.add(new MoveFromArrayInstr(Rarr, index.getRegImm(list), Rtmp));

				// add branching instructions
				addBranchCode(list, (DoubleLabel) context, Rtmp);
			default:
				assert(false);
				throw new Exception();
			}
		}
		return list;
	}

	
	/**
	 * a
	 * --
	 *	member-var: translateMemberVar(this, a)
	 *	local:		translaveVar(a_v{depth})
	 *	param:		translateVar(a)
	 *
	 */
	public List<LIREntry> visit(SimpleVar that, LoweringContext context)
			throws Exception {
		String id = that.getID();
		SymTabEntry e = that.getSymTab().resolve(id);
		List<LIREntry> list = new LinkedList<LIREntry>();

		if (e.isMemberVar()) {
			// move 'this' to a register
			RegOperand Rinst = new RegOperand();
			list.add(new MoveInstr(new MemOperand("this"), Rinst));

			// have translateMemberVar complete the work
			SymTabEntry eThis = that.getSymTab().resolve("this");
			translateMemberVar(list, Rinst,
					getClassInfoByType(eThis.getType()), 
					that.getID(), that.isLvalue(), context);
		} 
		else if (e.isLocalVar()) {
			int depth = e.getDepth();
			translateVar(list, id + "_" + depth, that.isLvalue(), context);
		} 
		else if (e.isFormalParam()) {
			translateVar(list, id, that.isLvalue(), context);
		}
		else {
			throw new Exception();
		}
		return list;
	}

	
	/**
	 * a.b
	 * ---
	 * 		translateMemberVar(a.b)
	 */
	public List<LIREntry> visit(MemberVar that, LoweringContext context)
			throws Exception {
		// resolve instance
		Expression inst = that.getInstance();
		RegOperand Rinst = new RegOperand();
		List<LIREntry> list = inst.accept(this, Rinst);

		// have translateMemberVar complete the work
		translateMemberVar(list, Rinst, getClassInfoByExpr(inst), 
				that.getID(), that.isLvalue(), context);
		return list;
	}

	/**
	 * generates code that returns an immediate value to a context
	 * @param val the immediate value
	 * @param context the context
	 * @return the code
	 */
	private List<LIREntry> generateLiteralCode(ImmOperand val, 
		LoweringContext context) {
		
		switch (context.getKind()) {
		case REG:
			return new LinkedList<LIREntry>(
					new MoveInstr(val, (RegOperand) context));
		case AnyOperand:
			((AnyOperand)context).set(val);
			return new LinkedList<LIREntry>();
		default:
			assert (false);
			return null;	
		}
	}
	
	
	/**
	 * N
	 * --
	 * 		Move N, dest
	 */
	public List<LIREntry> visit(IntLiteral that, LoweringContext context)
			throws Exception {
		return generateLiteralCode(new IntImmediate(that.getValue()),context);
	}

	
	/**
	 * null
	 * ----
	 * 		Move 0, dest
	 * 
	 */
	public List<LIREntry> visit(NullLiteral that, LoweringContext context)
			throws Exception {
		return generateLiteralCode(new IntImmediate(0),context);
	}

	
	/**
	 * "foo"
	 * ------
	 * 		Move literal_of("foo"), dest
	 */
	public List<LIREntry> visit(StringLiteral that, LoweringContext context)
			throws Exception {
		/*
		Label strLiteral = 
				new Label(root.getStringLiterals().get(that.getValue()));
		return generateLiteralCode(strLiteral,context);
		*/
		MemOperand strLiteral = 
			new MemOperand(root.getStringLiterals().get(that.getValue()));
		switch (context.getKind()) {
		case REG:
			return new LinkedList<LIREntry>(
					new MoveInstr(strLiteral, (RegOperand)context));
		case AnyOperand:
			((AnyOperand)context).set(strLiteral);
			return new LinkedList<LIREntry>();
		default:
			assert (false);
			return null;	
		}
	}
	

	/**
	 * true/false
	 * -----------
	 * 		Jump truelabel / Jump FalseLabel / NOP
	 * 
	 * 		Move 1/0, Rdest
	 * 
	 */
	public List<LIREntry> visit(BoolLiteral that, LoweringContext context)
			throws Exception {

		switch (context.getKind()) {
		case REG:
		case AnyOperand:
			ImmOperand val = new IntImmediate(that.getValue()?1:0);
			return generateLiteralCode(val,context);
		case DBLLabel:
			DoubleLabel dblLabel = (DoubleLabel) context;
			Label destLabel = that.getValue() 
					? dblLabel.trueLabel : dblLabel.falseLabel;
			return (destLabel == null) 
					? new LinkedList<LIREntry>() 
					: new LinkedList<LIREntry>(new JumpInstr(destLabel));
		default:
			assert(false);
			throw new Exception();
		}
	}
	

	/**
	 * a.length
	 * ---------
	 * 		visit(a,RArr)
	 * 		ArrayLength	Rarr, Rdest
	 * 
	 */
	public List<LIREntry> visit(LengthExpr that, LoweringContext context)
			throws Exception {
		RegOperand Rarr = new RegOperand();
		List<LIREntry> list = that.getArray().accept(this, Rarr);
		switch (context.getKind()) {
		case AnyOperand:
		case REG:
			list.add(new ArrayLengthInstr(Rarr, getRegToSave(context)));
			break;
		default:
			throw new Exception();
		}
		return list;
	}
	

	/**
	 * new Type[expr];
	 * ------------
	 * 		visit(expr,Rsize)
	 * 		Library __allocateArray(Rsize), Rdest
	 */
	public List<LIREntry> visit(NewArrayExpr that, LoweringContext context)
			throws Exception {
		assert(ContextKind.CanBeReg.contains(context.getKind()));
		
		// translate the size expression
		RegOperand Rsize = new RegOperand();
// TODO compute as any operand
		List<LIREntry> list = that.getSize().accept(this, Rsize);

		// multiply size by 4
		list.add(new BasicInstr(Ops.Mul, new IntImmediate(4), Rsize));

		// make parameters list of Library call
		List<Operand> params = new ArrayList<Operand>();
		params.add(Rsize);

		// emit function call instruction
		switch (context.getKind()) {
		case AnyOperand:
		case REG:
			RegOperand Rdest = getRegToSave(context);
			list.add(new LibraryInstr("allocateArray", params, Rdest));
			return list;
		default:
			throw new Exception();
		}
	}

	/**
	 * new A();
	 * --------
	 * 		Library __allocateObject(size-of-A), Rdest
	 * 		MoveField	_DV_A, Rdest.0
	 * 		
	 */
	public List<LIREntry> visit(NewClassExpr that, LoweringContext context)
			throws Exception {
		assert(ContextKind.CanBeReg.contains(context.getKind()));

		// make parameters list of Library call
		ClassInfo classInfo = getClassInfo(that.getClassID());
		List<Operand> params = new ArrayList<Operand>();
		int size = classInfo.getSize();
		params.add(new IntImmediate(size));

		RegOperand Rdest = getRegToSave(context);

		// emit function call instruction
		List<LIREntry> list = new LinkedList<LIREntry>(
				new LibraryInstr("allocateObject", params, Rdest));

		// save dispatch vector
		list.add(new MoveToFieldInstr(
				new Label(classInfo.getDVName()), 
				Rdest, new IntImmediate(0)));
		
		return list;
	}


	/**
	 * this
	 * -----
	 * 		Move this, Rdest
	 */
	public List<LIREntry> visit(ThisExpr that, LoweringContext context)
			throws Exception {
		
		MemOperand op = new MemOperand("this");
		switch (context.getKind()) {
		case REG:
			RegOperand Rdest = (RegOperand)context;
			return new LinkedList<LIREntry>(new MoveInstr(op, Rdest));
		case AnyOperand:
			((AnyOperand)context).set(op);
			return new LinkedList<LIREntry>();
		default:
			assert(false);
			throw new Exception();
		}

	}
		

	/**
	 * -a 
	 * ---------
	 * 		visit(a,Rdest)
	 * 		Neg	Rdest
	 * !a
	 * ---------
	 * 		visit(a,<true-false labels swapped>)
	 * 		
	 */
	public List<LIREntry> visit(UnaryExpr that, LoweringContext context)
			throws Exception {

		List<LIREntry> list = null;

		Operator op = that.getOp();
		RegOperand Rdest;

		switch (op) {
		case MINUS:
			// TODO optimize negating immediates
			switch (context.getKind()) {
			case REG:
			case AnyOperand:
				// TODO compute as any operand
				Rdest = getRegToSave(context);
				list = that.getOperand().accept(this, Rdest);
				list.add(new BasicInstr(Ops.Neg, Rdest));
				break;
			default: 
				assert(false);
				throw new Exception();
			}
			break;
		case LNEG:
			switch (context.getKind()) {
			case REG:
			case AnyOperand:
				// xor with 1
				// TODO compute as any operand
				Rdest = getRegToSave(context);
				list = that.getOperand().accept(this, Rdest);
				list.add(new BasicInstr(Ops.Xor, new IntImmediate(1), Rdest));
				break;
			case DBLLabel:
				// swap labels!!
				DoubleLabel dblLabel = (DoubleLabel)context;
				list = that.getOperand().accept(this, 
						new DoubleLabel(dblLabel.falseLabel,dblLabel.trueLabel));
				break;
			default:
				assert(false);
				throw new Exception();
			}
			break;
		default:
			assert(false);
			throw new Exception();
		}
		return list;
	}
	
	
	/**
	 * Arithmetic:
	 * =============================
	 * for op in {+,-,*,/,%}:
	 *
	 * a op b 
	 * ---------
	 * 		visit(a,Rdest)               (every instruction visiting a and b)
	 * 		visit(b,Rtmp)
	 * 		op	Rtmp --> Rdest
	 * 
	 * 
	 * Strings:
	 * 
	 * a + b
	 * 
	 * 
	 * 
	 * Boolean short-circuit:
	 * ==============================
	 * 
	 * a && b (lTrue, lFalse)
	 * -----------------------
	 * 		visit(a, null, lFalse)
	 * 		visit(b, lTrue, lFalse)
	 * 
	 * a || b
	 * ---------
	 * 		visit(a, lTrue, null)
	 * 		visit(b, lTrue, lFalse)
	 * 
	 * 
	 * 
	 * Comparison:
	 * ==============================
	 * a < b
	 * ---------
	 * 		Compare	Rres1 Rres2 => Compare = Rres2 - Rres1
	 * 							   if Compare > 0
	 * 									Jump TrueLabel
	 * 							   else
	 * 									Jump FalseLabel
	 *		JumpLE FalseLabel
	 * a <= b
	 * ---------
	 * 		Compare Rres1 Rres2
	 * 		JumpL  FalseLabel
	 * a > b
	 * ---------
	 * 		Compare Rres1 Rres2
	 * 		JumpGE  FalseLabel
	 * 
	 * a >= b
	 * ---------
	 * 		Compare Rres1 Rres2
	 * 		JumpG  FalseLabel
	 * 
	 * a == b
	 * ---------
	 * 		Compare Rres1 Rres2
	 * 		JumpFalse  FalseLabel
	 * 
	 * a != b
	 * ---------
	 * 		Compare Rres1 Rres2
	 * 		JumpTrue  FalseLabel
	 * 
	 * 
	 */
	public List<LIREntry> visit(BinaryExpr that, LoweringContext context)
			throws Exception {

		List<LIREntry> list = new LinkedList<LIREntry>();
		Operator op = that.getOp();

		if (Operator.BinaryMathOps.contains(op)) {
			assert( ContextKind.CanBeReg.contains(context.getKind()) );

			// evaluate both opernads of the expression:
			// evaluate the right to temporary register
			// and the right to the accumulator
			
// TODO weighted allocation
			
			
			if (op.equals(Operator.PLUS) 
					&& isString(that.getLeft()) && isString(that.getRight())) {

				// send the arguments as parameters to the 
				// concatination function
				AnyOperand str1 = new AnyOperand();
				AnyOperand str2 = new AnyOperand();

				list.addAll(that.getLeft().accept(this, str1));
				list.addAll(that.getRight().accept(this, str2));
				
				List<Operand> params = new ArrayList<Operand>();
				params.add(str1.getOp());
				params.add(str2.getOp());
				
				RegOperand Rdest = getRegToSave(context);
				list.add(new LibraryInstr("stringCat", params, Rdest));
				// TODO reuse register from arguments to result, if possible
			}
			else if (Operator.CommutativeOps.contains(op) 
					&& context.getKind().equals(ContextKind.AnyOperand)) {
				// commutative: save the volunteer to a register
				AnyOperand left = new AnyOperand();
				AnyOperand right = new AnyOperand();
				
				list.addAll(that.getLeft().accept(this, left));
				list.addAll(that.getRight().accept(this, right));
				
				// decide which one is src and who is dest
				Operand src;
				RegOperand Rdest;
				if (left.isReg() || !right.isReg()) {
					Rdest = left.getReg(list); 
					src = right.getOp();
				}
				else {
					Rdest = right.getReg(list); 
					src = left.getOp();
				}
				((AnyOperand)context).set(Rdest);
				switch (op) {
				case PLUS:
					list.add(new BasicInstr(Ops.Add, src, Rdest));
					break;
				case MUL:
					list.add(new BasicInstr(Ops.Mul, src, Rdest));
					break;
				default:
					assert (false);
				}
			}
			else {
				// non-commutative: save left side to a register anyway
				AnyOperand tmp = new AnyOperand();
				RegOperand Rdest = getRegToSave(context);
				list.addAll(that.getLeft().accept(this, Rdest));
				list.addAll(that.getRight().accept(this, tmp));
				switch (op) {
				case PLUS:
					list.add(new BasicInstr(Ops.Add, tmp.getOp(), Rdest));
					break;
				case MUL:
					list.add(new BasicInstr(Ops.Mul, tmp.getOp(), Rdest));
					break;
				case MINUS:
					list.add(new BasicInstr(Ops.Sub, tmp.getOp(), Rdest));
					break;
				case DIV:
					list.add(new BasicInstr(Ops.Div, tmp.getOp(), Rdest));
					break;
				case MOD:
					list.add(new BasicInstr(Ops.Mod, tmp.getOp(), Rdest));
					break;
				default:
					assert (false);
				}
			}
		}
		else if (Operator.BoolOps.contains(op)) 
		{
			DoubleLabel labels;
			switch (context.getKind()) {
			case REG:
			case AnyOperand:
				labels = new DoubleLabel(null,new Label());
				break;
			case DBLLabel:
				labels = (DoubleLabel)context;
				break;
			default:
				assert(false);
				throw new Exception();
			}

			if (Operator.LtGtOps.contains(op) || Operator.EqNEqOps.contains(op)) {
				JumpCondition condT=null, condF=null, condRT=null, condRF=null;
				
		// TODO make it more efficient with masks, bits...
				switch (op) {
				case GT:
					condT = JumpCondition.GREATER;		condRT = JumpCondition.LESSTHAN;
					condF = JumpCondition.LESSTHANEQUAL;condRF = JumpCondition.GREATEREQUAL;
					break;
				case GTE:
					condT = JumpCondition.GREATEREQUAL;	condRT = JumpCondition.LESSTHANEQUAL; 
					condF = JumpCondition.LESSTHAN;		condRF = JumpCondition.GREATER;
					break;
				case LT:
					condT = JumpCondition.LESSTHAN;		condRT = JumpCondition.GREATER;
					condF = JumpCondition.GREATEREQUAL;	condRF = JumpCondition.LESSTHANEQUAL;
					break;
				case LTE:
					condT = JumpCondition.LESSTHANEQUAL; condRT = JumpCondition.GREATEREQUAL;
					condF = JumpCondition.GREATER;		 condRF = JumpCondition.LESSTHAN;
					break;
				case NEQ:
					condT = condRT = JumpCondition.FALSE;
					condF = condRF = JumpCondition.TRUE;
					break;
				case EQ:
					condT = condRT = JumpCondition.TRUE;
					condF = condRF = JumpCondition.FALSE;
					break;
				default:
					assert(false);
				}

				// evaluate operand expressions
				AnyOperand right = new AnyOperand();
				AnyOperand left = new AnyOperand();

				list.addAll(that.getRight().accept(this, right));
				list.addAll(that.getLeft().accept(this, left));

				// add comparison instruction
				if (left.isReg() || !right.isReg()) {
					list.add(new BasicInstr(Ops.Compare, right.getOp(), left.getReg(list)));
					addBranchCode(list,labels,condT,condF);
				}
				else {
					list.add(new BasicInstr(Ops.Compare, left.getOp(), right.getReg(list)));
					addBranchCode(list,labels,condRT,condRF);
				}
			}
			else if (Operator.AndOrOps.contains(op)) {
				switch (op) {
				case AND:
					if (labels.falseLabel == null) {
						Label lFalse = new Label();
						list.addAll(that.getLeft().accept(this, 
								new DoubleLabel(null, lFalse)));
						list.addAll(that.getRight().accept(this, 
								new DoubleLabel(labels.trueLabel, lFalse)));
						list.add(new LabelDecl(lFalse));
					}
					else {
						list.addAll(that.getLeft().accept(this, 
								new DoubleLabel(null, labels.falseLabel)));
						list.addAll(that.getRight().accept(this, labels));
					}
					break;
				case OR:
					if (labels.trueLabel == null) {
						Label lTrue = new Label();
						list.addAll(that.getLeft().accept(this, 
								new DoubleLabel(lTrue, null)));
						list.addAll(that.getRight().accept(this, 
								new DoubleLabel(lTrue, labels.falseLabel)));
						list.add(new LabelDecl(lTrue));
					}
					else {
						list.addAll(that.getLeft().accept(this, 
								new DoubleLabel(labels.trueLabel, null)));
						list.addAll(that.getRight().accept(this, labels));
					}
					break;
				}
			}

			// if we are saving to a register, add 1/0 values
			if (ContextKind.CanBeReg.contains(context.getKind())) {
				RegOperand Rdest = getRegToSave(context); 
				Label lEnd = new Label();

				list.add(new MoveInstr(new IntImmediate(1),Rdest));
				list.add(new JumpInstr(lEnd));
				list.add(new LabelDecl(labels.falseLabel));
				list.add(new MoveInstr(new IntImmediate(0),Rdest));
				list.add(new LabelDecl(lEnd));
			}
		}
		else {
			assert (false);
		}
		return list;
	}

	/** helper functions * */
	private boolean isString(Expression expr) {
		return expr.getType().equals(StringType.getIt());
	}
	
	/**
	 * return a register to save to, from the context
	 * @param context the context object
	 * @return the register operand
	 */
	private RegOperand getRegToSave(LoweringContext context) {
		switch (context.getKind()) {
		case REG:
			return (RegOperand)context;
		case AnyOperand:
			RegOperand reg = new RegOperand();
			((AnyOperand)context).set(reg);
			return reg;
		default:
			assert (false);
			return null;
		}
	}

	/**
	 * builds a list of pair parameters to a static or virtual call
	 * @param list the instruction buffer
	 * @param args the argument expressions
	 * @param methodDecl the method declaration
	 * @return list of parameters to a static or virtual call
	 */
	private List<Pair<String, Operand>> buildParams(List<LIREntry> list,
			List<Expression> args, MethodDecl methodDecl) throws Exception {
		List<Pair<String, Operand>> params;
		Iterator<FormalDecl> formalIter;

		// initiallize arguments scanners
		params = new ArrayList<Pair<String, Operand>>();
		formalIter = methodDecl.getFormals().iterator();

		// collect the arguments
		for (Expression argExpr : args) {
			AnyOperand dest = new AnyOperand();
			list.addAll(argExpr.accept(this, dest));
			params.add(new Pair<String, Operand>(
					formalIter.next().getID(), dest.getOp()));
		}
		return params;
	}
	
	
	/**
	 * adds code that treats RboolValue as a boolean value operand
	 * that is translated in a double-label context
	 * @param list
	 * @param dblLabel
	 * @param RboolValue
	 */
	private void addBranchCode(List<LIREntry> list, DoubleLabel dblLabel,
			RegOperand RboolValue) {
		list.add(new BasicInstr(Ops.Compare, new IntImmediate(1), RboolValue));
		addBranchCode(list, dblLabel, JumpCondition.TRUE, JumpCondition.FALSE);
	}

	
	/**
	 * Adds to the list instructions that, based on a previous
	 * Compare instruction, jump to the true/false/both labels,
	 * handling the cases when one of the labels is null (if both
	 * are null no code is added)
	 * @param list the lir code buffer
	 * @param dblLabel the destination labels
	 * @param jumpTrue the true-label condition
	 * @param jumpFalse the false-label condition
	 */
	private void addBranchCode(List<LIREntry> list, DoubleLabel dblLabel,
			JumpCondition jumpTrue, JumpCondition jumpFalse) {
		if (dblLabel.falseLabel != null)
			list.add(new JumpInstr(dblLabel.falseLabel, jumpFalse));
		if (dblLabel.trueLabel != null)
			list.add(new JumpInstr(dblLabel.trueLabel, jumpTrue));
		// remark: this can be improve by sometimes replacing one
		// of the conditional jumps with an undonditional one
	}

	
	/**
	 * translateMemberVar(a.b)
	 * -----------------------
	 * 		visit(a,Rinst)
	 * 		if 	l-value: MoveField Rop, Rinst.offset-of(b)
	 * 				else: MoveField Rinst.offset-of(b), Rop
	 * 
	 */
	private void translateMemberVar(List<LIREntry> list, RegOperand Rinst,
			ClassInfo classInfo, String id, boolean isLvalue,
			LoweringContext context) throws Exception {
		// get the field offset from class info
		ImmOperand Offs = new IntImmediate(classInfo.getFieldOffset(id));

		// handle L-values and R-values differently
		if (isLvalue) {
			// field <- value
			Operand src = null;
			switch (context.getKind()) {
			case REG:
				src = (RegOperand)context;
				break;
			case AnyOperand:
				src = ((AnyOperand)context).getRegImm(list);
				break;
			default:
				assert (false);
			}
			list.add(new MoveToFieldInstr(src, Rinst, Offs));
		} else {
			// move from field, or branch
			switch (context.getKind()) {
			case REG:
			case AnyOperand:
				// reg <- field
				RegOperand Rdest = getRegToSave(context);
				list.add(new MoveFromFieldInstr(Rinst, Offs, Rdest));
				break;
			case DBLLabel:
				// branch on field value
				RegOperand Rval = new RegOperand();
				list.add(new MoveFromFieldInstr(Rinst, Offs, Rval));
				addBranchCode(list, (DoubleLabel) context, Rval);
				break;
			default:
				assert(false);
				throw new Exception();
			}
		}
	}
	
	
	/**
	 * translates a variable token, based on the context and
	 * R/L value.
	 * @param list the intruction list buffer
	 * @param id the variable ID
	 * @param isLvalue 
	 * @param context the context (REG or DBLBuffer)
	 * @throws Exception 
	 */
	private void translateVar(List<LIREntry> list, String id, boolean isLvalue,
			LoweringContext context) throws Exception {
		// make memory operand from the ID
		MemOperand varOp = new MemOperand(id);

		// save to var / read from var
		if (isLvalue) {
			// var <- reg
			// field <- value
			Operand src = null;
			switch (context.getKind()) {
			case REG:
				src = (RegOperand)context;
				break;
			case AnyOperand:
				src = ((AnyOperand)context).getRegImm(list);
				break;
			default:
				assert (false);
			}
			list.add(new MoveInstr(src, varOp));
		}
		else {
			RegOperand Rtmp;
			switch (context.getKind()) {
			case REG:
				// reg <- var
				list.add(new MoveInstr(varOp, (RegOperand) context));
				return;
			case AnyOperand:
				((AnyOperand)context).set(varOp);
				break;
			case DBLLabel:
				// compare the variable to 1
				Rtmp = new RegOperand();
				list.add(new MoveInstr(varOp, Rtmp));
				// add branching instructions
				addBranchCode(list, (DoubleLabel) context, Rtmp);
				return;
			default:
				assert(false);
				throw new Exception();
			}
		}
	}

	
	/**
	 * a <- b
	 * ------
	 * 		visit(b, ?)
	 * 		visit(a, ?)
	 *
	 */
	public List<LIREntry> translateAssignment(Variable dest, Expression source)
			throws Exception {
		assert ((dest.getType() != null) && (source.getType() != null));

		List<LIREntry> list;
		
		// compute the source expression in a free context
		AnyOperand val = new AnyOperand();
		list = source.accept(this, val);

		// ask the destination to save the value
		list.addAll(dest.accept(this, val));
		return list;
	}
	
	
	/**
	 * get class info by class name
	 * @param classID the class ID
	 * @return the class info
	 */
	private ClassInfo getClassInfo(String classID) {
		SymTabEntry e = root.getSymTab().resolve(classID);
		return ((ClassDecl) e.getDeclNode()).getClassInfo();
	}

	
	/**
	 * get class info record by an expression object
	 * @param expr
	 * @return
	 */
	private ClassInfo getClassInfoByExpr(Expression expr) {
		ClassType classType = (ClassType) expr.getType();
		return classType.getDecl().getClassInfo();
	}

	/**
	 * get class info record by a class type object
	 * 
	 * @param classType
	 * @return
	 */
	private ClassInfo getClassInfoByType(Type classType) {
		return ((ClassType) classType).getDecl().getClassInfo();
	}
}
